package com.datastructure.test.oddandevenresort;

import java.util.ArrayList;

public class OddAndEvenResort {

    ArrayList<Integer> odds = new ArrayList<>();
    ArrayList<Integer> evens = new ArrayList<>();
    public static void main(String[] args) {

    }

    public ListNode oddEvenList (ListNode head) {
        // write code here
        ListNode cur = null;
        ListNode temp = null;
        int i = 0;
        while (head!=null){
            if(i%2==0){
                evens.add(head.val);
            } else {
                odds.add(head.val);
            }
            i++;
            head=head.next;
        }
        if(odds.size()==0){
            for (int j = evens.size() - 1; j >= 0; j--) {
                cur=new ListNode(evens.get(j));
                cur.next=temp;
                temp=cur;
            }
            return cur;
        } else {
            for (int j = odds.size() - 1; j >= 0; j--) {
                cur=new ListNode(odds.get(j));
                cur.next=temp;
                temp=cur;
            }
            for (int j = evens.size() - 1; j >= 0; j--) {
                cur=new ListNode(evens.get(j));
                cur.next=temp;
                temp=cur;
            }
        }

        return cur;
    }
}

class ListNode {
    int val;
    ListNode next = null;
    public ListNode(int val) {
      this.val = val;
    }
}
